package com.zhoux.algorithm;

/**
 * @author taoyi
 * @version 1.0
 * @date 2021/3/16 15:14
 *
 * 本类实现了二分查找
 */
public class Dichotomy_Search {
    private int[] array;

    public Dichotomy_Search(int[] array) {
        this.array = array;
    }

    public int search_Recursion(int target){ // public方法，提供给外部调用
        if (array != null){
            return search_Recursion(target, 0, array.length-1);
        }
        return -1;
    }


    /**
     * 递归实现二分查找
     * @param target 需要查找的目标
     * @param start 开始下标
     * @param end 结束下标
     * @return
     */
    private int search_Recursion(int target, int start, int end) {
        if (start > end){ // 如果开始下标大于结束下标，表示没有找到，返回-1
            return -1;
        }
//        int mid = (start + end ) / 2; // 取中间值
        int mid = (start + end ) >> 1; // 取中间值,位运算，速度更快
        if (array[mid] == target){ // 相等表示找到目标，返回目标下标
            return mid;
        }else if (array[mid] > target){ // 目标小于中间值
            return search_Recursion(target, start, mid-1);
        }else { // 目标大于中间值
            return search_Recursion(target, mid+1,end);
        }
    }


    /**
     * 非递归实现二分查找
     * @param target 查找目标
     * @return
     */
    public int search(int target){
        if (array==null){
            return -1;
        }
        int start = 0;
        int end = array.length-1;

        while (start <= end){
//            int mid = (start + end ) / 2;
            int mid = (start + end ) >> 1;
            if (array[mid] == target){
                return mid;
            }else if (array[mid] < start){
                start = mid + 1;
            }else {
                end = mid - 1;
            }
        }
        return -1;
    }
}

